package TDAArbolBinario;

import java.util.Iterator;

import TDALista.BoundaryViolationException;
import TDALista.InvalidPositionException;
import TDALista.Position;
/**
 * Implementa parcialmente un BinaryTree mediante una ED que mantiene referencias al padre, hijo izquierdo y derecho de la posición.
 * @author FJoaquin (federico.joaquin@cs.uns.edu.ar)
 * @param <E> Tipo de dato de los rótulos de los nodos de árbol.
 */
public class ArbolBinario<E> implements BinaryTree<E> {
	protected BTPosition<E> raiz;
	protected int tamaño;
	/**
	 * Inicializa un árbol binario vacío.
	 */
	public ArbolBinarioClase(){ 
		tamaño = 0;
		raiz = null;
	}
	/**
	 * Inicializa un árbol binario de tamaño uno.
	 * @param rot Rótulo de la raíz del árbol creado.
	 */
	public ArbolBinarioClase(E rot){ 
		tamaño = 1;
		raiz = new BTNodo<E>(rot, null);
	}
	/**
	 * Inicializa un árbol binario completo dada una altura y un iterador de elementos.
	 * Para esto, clona la estructura y elementos de otro árbol binario completo que es recorrido mediante el iterador, siguiendo un recorrido en preorden. 
	 * @param it Iterador del árbol binario completo a clonar, siguiendo un recorrido en pre-orden.
	 * @param altura Altura correspondiente al árbol binario completo a clonar.
	 */
	public ArbolBinarioClase(Iterator<E> it, int altura){
		E rotulo;
		//Si el árbol a clonar tiene al menos un elemento, se crea la raíz.
		if (it.hasNext()){
			rotulo = it.next();
			raiz = new BTNodo<E>(rotulo, null);
			tamaño = 1;
			//Si la altura de la raíz es mayor que cero, se clona los subárboles a partir de esta.
			if (altura>0)
				clonar_arbol_completo(raiz, it, altura-1);
		}
	}
	/**
	 * Clona el subárbol binario completo a partir de la posición padre.
	 * Para esto considera la altura de las raíces de los subárboles a clonar, y el recorrido en preorden que sigue el iterador de elementos del árbol binario clonado.
	 * @param padre Nodo al que se agregarán el subárbol izquierdo y derecho.
	 * @param it Iterador del subárbol binario completo a clonar, siguiendo un recorrido en pre-orden.
	 * @param altura Altura correspondiente del nodo padre en el árbol binario clonado.
	 */
	protected void clonar_arbol_completo(BTPosition<E> padre, Iterator<E> it, int altura) {
		E rotulo;
		tamaño += 2;
		//Clonación de las hojas del árbol.
		if (altura == 0){
			rotulo = it.next();
			padre.setLeft(new BTNodo<E>(rotulo, padre));
			rotulo = it.next();
			padre.setRight(new BTNodo<E>(rotulo, padre));
		}else {
			//Clonación de nodos internos del árbol.
			rotulo = it.next();
			padre.setLeft(new BTNodo<E>(rotulo, padre));
			clonar_arbol_completo(padre.getLeft(), it, altura-1);
			rotulo = it.next();
			padre.setRight(new BTNodo<E>(rotulo, padre));
			clonar_arbol_completo(padre.getRight(), it, altura-1);
		}
	}
	/**
	 * Corresponde a la implementación de operación Attach() según Goodrich & Tamassia.
	 * En el contexto de Estructuras de datos, esta implementación es considerada inválida.
	 */
	protected void attach_goodrich_tamassia(Position<E> p, BinaryTree<E> t1, BinaryTree<E> t2) throws InvalidPositionException {
		BTPosition<E> raiz_local = checkPosition(p);
		if (raiz_local.getLeft() != null || raiz_local.getRight() != null)
			throw new InvalidPositionException("La posicion no corresponde a un nodo hoja");
		
		BTPosition<E> raiz_t1 = null;
		BTPosition<E> raiz_t2 = null;
		
		try {
			if (!t1.isEmpty())
				raiz_t1 = checkPosition(t1.root());
			if (!t2.isEmpty())
				raiz_t2 = checkPosition(t1.root());
			
			raiz_local.setLeft(raiz_t1);
			raiz_local.setRight(raiz_t2);
			
			tamaño += t1.size() + t2.size();
		}catch(EmptyTreeException e) {}
	}
	
	@Override
	public void attach(Position<E> p, BinaryTree<E> t1, BinaryTree<E> t2) throws InvalidPositionException {
		BTPosition<E> raiz_local = checkPosition(p);
		if (raiz_local.getLeft() != null || raiz_local.getRight() != null)
			throw new InvalidPositionException("La posicion no corresponde a un nodo hoja");
		
		try {
			//Clonación de T1 como subárbol izquierdo
			if (!t1.isEmpty()) {
				Position<E> raiz_t1 = t1.root();
				BTPosition<E> hi_raiz_local = new BTNodo<E>(raiz_t1.element(), raiz_local);
				raiz_local.setLeft(hi_raiz_local);
				clonar(raiz_local.getLeft(), raiz_t1, t1);
			}
			
			//Clonación de T2 como subárbol derecho
			if (!t2.isEmpty()) {
				Position<E> raiz_t2 = t2.root();
				BTPosition<E> hd_raiz_local = new BTNodo<E>(raiz_t2.element(), raiz_local);
				raiz_local.setRight(hd_raiz_local);
				clonar(raiz_local.getRight(), raiz_t2, t2);
			}
		}catch(EmptyTreeException e) {
			raiz_local.setLeft(null);
			raiz_local.setRight(null);
		}
	}
	/**
	 * Método auxiliar utilizado por attach.
	 * Clona los hijos de T a partir de la posición padre_t, y agrega a estas clonaciones como hijos de padre_local.
	 * @param padre_local Posición a la que se le agregan la clonación de los hijos izquierdo y derecho de padre_t en T.
	 * @param padre_t Posición de T que señala el padre de los hijos izquierdo y derecho a clonar.
	 * @param t BinaryTree que contiene al nodo padre_t, y del que se clonarán los nodos hijos izquierdo y derecho de padre_t.
	 */
	protected void clonar(BTPosition<E> padre_local, Position<E> padre_t, BinaryTree<E> t) {
		try {
			//Si existe hijo izquierdo en T de padre_t, se clona este y el subárbol a partir del hijo izquierdo de padre_t.
			if (t.hasLeft(padre_t)) {
				Position<E> hi_padre_t = t.left(padre_t);
				BTPosition<E> hi_padre_local = new BTNodo<E>(hi_padre_t.element(), padre_local);
				padre_local.setLeft(hi_padre_local);
				clonar(hi_padre_local, hi_padre_t, t);
			}
			
			//Si existe hijo derecho en T de padre_t, se clona este y el subárbol a partir del hijo derecho de padre_t.
			if (t.hasRight(padre_t)) {
				Position<E> hd_padre_t = t.right(padre_t);
				BTPosition<E> hd_padre_local = new BTNodo<E>(hd_padre_t.element(), padre_local);
				padre_local.setRight(hd_padre_local);
				clonar(hd_padre_local, hd_padre_t, t);
			}
		}catch(InvalidPositionException | BoundaryViolationException e) {
			padre_local.setLeft(null);
			padre_local.setRight(null);
		}
	}
	/**
	 * Valida que la ED interna de la posición se corresponda con la utilizada por la implementación actual.
	 * @param p Posición a validar.
	 * @return Referencia a BTPosiciin de la posicion validada, si esta es válida.
	 * @throws InvalidPositionException Si la posición parametrizada no corresponde con la implementación actual, o referencia a null, o fue eliminada con anterioridad (rótulo null).
	 */
	protected BTPosition<E> checkPosition(Position<E> p) throws InvalidPositionException{
		BTPosition<E> toReturn = null;
		try {
			toReturn = (BTNodo<E>) p;
			if (toReturn == null || toReturn.element() == null)
				throw new InvalidPositionException();
		}catch(ClassCastException e) {
			throw new InvalidPositionException();
		}
		return toReturn;
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return 0;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public Iterator<E> iterator() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Iterable<Position<E>> positions() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public E replace(Position<E> v, E e) throws InvalidPositionException {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Position<E> root() throws EmptyTreeException {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Position<E> parent(Position<E> v) throws InvalidPositionException, BoundaryViolationException {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Iterable<Position<E>> children(Position<E> v) throws InvalidPositionException {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public boolean isInternal(Position<E> v) throws InvalidPositionException {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean isExternal(Position<E> v) throws InvalidPositionException {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean isRoot(Position<E> v) throws InvalidPositionException {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public Position<E> left(Position<E> v) throws InvalidPositionException, BoundaryViolationException {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Position<E> right(Position<E> v) throws InvalidPositionException, BoundaryViolationException {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public boolean hasLeft(Position<E> v) throws InvalidPositionException {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean hasRight(Position<E> v) throws InvalidPositionException {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public Position<E> createRoot(E r) throws InvalidOperationException {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Position<E> addLeft(Position<E> v, E r) throws InvalidOperationException, InvalidPositionException {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Position<E> addRight(Position<E> v, E r) throws InvalidOperationException, InvalidPositionException {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public E remove(Position<E> v) throws InvalidOperationException, InvalidPositionException {
		// TODO Auto-generated method stub
		return null;
	}
}
